1. Field of the Invention
The present invention relates to a new circuit type transition signaling circuit comprised of Muller C elements used for pipeline control and other purposes, and an arbitrator which arbitrates the contention of devices using the transition signaling control circuit, which is used when the devices share a predetermined resource, such as a bus.
2. Description of Related Art
Prior art related to such a field is, for example, those stated in the following documents.
Document 1: Magazine “bit”, Vol. 22, No. 3, published by Kyoritsu Publishing, pp. 246-268; Paper from Commemorative Lecture on Winning 1998 ACM Turing Prize (Ivan E. Sutherland: Micro-pipelines, CACM, Vol. 32, No. 6, pp. 720-378)
Document 2: Japanese Patent Laid-Open No. 6-90165
Document 3: Japanese Patent Laid-Open No. 6-96019
Document 4: Japanese Patent Laid-Open No. 9-244890
Document 5: Japanese Patent Laid-Open No. 11-3206
For example, as Document 1 states, a concept called “transition signaling” recently emerged as a concept which counters conventional clocked logic. This is a field of asynchronous design methodologies.
Conventional clocked logic is based on the premise that all signals are binary and the time thereof can be discrete. This means that Boolean logic, which is a logic to express the input conditions of a logic circuit and the result by algebraic expressions, can be applied, therefore circuit design is easier even for a relatively large scale circuit. In asynchronous design methodologies as well, all signals are binary, but the time thereof is not discrete, which is different from conventional clocked logic. As a result, the following three advantages are noteworthy.
The first advantage is that problems due to clock skew, such as the generation of a glitch in a large scale circuit, can be controlled.
The second advantage is that the power consumption of a logic circuit can be controlled in the case of asynchronous design methodologies since only the part of a logic circuit required for calculation need be operated, while in the case of clocked logic, the clock operation is continuously active for parts unnecessary for logic operation, so the power consumption of a logic circuit is high.
The third advantage is that the average speed of logic processing can be secured in the case of asynchronous design methodologies, but in the case of clocked logic, the speed of all logic processing can be controlled by the critical path (longest path).
The transition signaling circuit is comprised of modules which process the logical combination of events. In transition signaling, the transition of the logical value of the signal to both direction, that is, the rise transition and the fall transition of the signal, have the same meaning, and this rise transition and fall transition are called an “event”. In the transition signaling method, the rise transition and the fall transition are not distinguished, but both edges of rise and fall are used as a trigger event, so potentially a two-times faster speed can be implemented compared with a conventional clock control method.
As Document 1 states, the Muller C element, for example, is one of the transition signaling circuits, providing an AND function for a transition event. Other transition signaling circuits include an XOR element, which provides an OR function of a transition event, and a TOGGLE element.
FIG. 7(A) and FIG. 7(B) are block diagrams of examples of a conventional Muller C element with an inverter, which is one transition signaling circuit, where FIG. 7(A) is a logical symbol diagram and FIG. 7(B) is a logical circuit diagram.
In the Muller C element with an inverter (i.e. inverter-provided Muller C element) 10, transition signals, such as the two request events ReqIn 1 and ReqIn 2, are supplied to the two input terminals thereof as input signals, and the request event ReqOut 1, which is a transition signal, is output from the output terminal thereof. This Muller C element with an inverter 10 is comprised of the inverter circuit 11 for signal inversion, the two input type first, second and third AND gate circuits 12, 13 and 14, and a three input type OR gate 15.
Request event ReqIn 2 to be input is inverted by the inverter circuit 11, and the second and third AND gate circuits 13 and 14 are connected to the output terminal. The request events ReqIn 1 and ReqOut 1 are input to the first AND gate circuit 12. The request event ReqIn 1 and the output signal of the inverter circuit 11 are input to the AND gate circuit 13. The output signal of the inverter circuit 11 and the request event ReqOut 1 are input to the AND gate circuit 14. These AND gate circuits 12, 13 and 14 are connected to the OR gate 15, and the request event ReqOut 1 is output from the output terminal of the OR gate 15 circuit. The AND gate circuit 12 and the OR gate circuit 15 constitute a latch circuit, and the AND gate circuit 14 and the OR gate circuit 15 also constitute a latch circuit.
In the case of such a Muller C element with an inverter 10, when the two input request events ReqIn 1 and ReqIn 2 have different values (e.g. logic level “H” and “L”) from each other, a value the same as the request event ReqIn 1 is output from the OR gate circuit 15 as an output request event ReqOut 1, and the value of this output is maintained in the latch circuit comprised of the AND gate circuit 12 and the OR gate circuit 15, or in the latch circuit comprised of the AND gate circuit 14 and the OR gate circuit 15, even if one of the input request events ReqIn 1 and ReqIn 2 changes later. When the two input request events ReqIn 1 and ReqIn 2 have the same value (e.g. logic level “H” and “H”, or logic level “L” and “L”) and if one of the inputs changes later, a value the same as the request event ReqIn 1 is output from the OR gate circuit 15 as an output request event ReqOut 1.
It is not assumed that both of the two input request events ReqIn 1 and ReqIn 2 change simultaneously, which is the same as the case of a reset/set type flip-flop.
As mentioned above, transition signals, such as ReqIn 1, ReqIn 2 and ReqOut 1, can be regarded as an event for a logical unit, and the Muller C element operates as an AND gate circuit for the event. The Muller C element with an inverter, on the other hand, transfers an event only when events having different logic from each other occur to both of the inputs. Fundamentally this creates a directional flow of events.
As Document 1 states, a pipeline is referred to as a device configuration to process data in a work flow. In the pipeline, data is stored and processed. The pipeline is operated by clock control (each section is operated according to a clock distributed from the outside) or is driven by an event (each section is independently operated each time a local event is generated).
Some kinds of pipelines are inelastic, where the data volume inside the pipeline is fixed. In the case of an inelastic pipeline, the speed of input and the speed of output of a signal must accurately match, therefore this pipeline operates just like a shift register when processing logic is excluded.
In the case of an elastic pipeline, on the other hand, the data volume inside the pipeline is variable, and the speed of input and the speed of output of a signal constantly changes depending on the buffering. The elastic pipeline operates as an FIFO (First-In-First-Out) memory when the processing logic is excluded. An elastic pipeline with a simple configuration driven by an event (regardless the presence and absence of the requirements of internal processing) is called a “micro-pipeline”.
FIG. 8 is a conceptual diagram depicting a control circuit of the conventional micro-pipeline stated in Document 1.
This control circuit of the micro-pipeline has the left side block 20-1 and the right side block 20-2 shown in FIG. 8. The left side block 20-1 has a Muller C element with an inverter 10-1 having the same configuration as shown in FIG. 7 where the request event Req (1), which is a transition signal, and the response event Ack (2), which is a transition signal from the right side block 20-2, are input. From the output terminal of this Muller C element with an inverter 10-1, the response event Ack (1), which is a transition signal, is output. The delay element 21-1 which delays the response event Ack (1) for the delay time DELAY 1 and outputs the request event Req (2), which is a transition signal, is connected to the output terminal of the Muller C element with an inverter 10-1.
In the same way, the right side block 20-2 has a Muller C element with an inverter 10-2, the same as shown in FIG. 7, where the request event Req (2), which is a transition signal, and the response event Ack (3), which is a transition signal, are input. The Muller C element with an inverter 10-1 and the delay element 21-2 are connected to this output terminal. The delay element 21-2 inputs the response event Ack (2), which is a transition signal output from the Muller C element with an inverter 10-2, delays this for the delay time DELAY 2, and outputs the request event Req (3), which is a transition signal.
In this pipeline, a set of connection circuits, where the left side block 20-1 and the right side block 20-2 are connected in this sequence, is one unit, and many other sets are sequentially connected before and after this one-unit set.
In FIG. 8, the logic circuit to be controlled by the control circuit of the micro-pipeline is omitted, but the data flow (from the input data Din to the output data Dout), which passes through the logic circuit, is indicated by the dashed line. In Document 1, a latch circuit, decoding circuit, and multiplication circuit are shown as an example of the logic circuit to be controlled.
FIG. 9 is a timing waveform diagram depicting the operation of the control unit of the micro-pipeline in FIG. 8. Now the operation of the control circuit of the micro-pipeline in FIG. 8 will be described with reference to FIG. 9.
As described above, the control circuit of the micro-pipeline in FIG. 8 is comprised of a combination of two blocks, where both the left side block 20-1 and the right side block 20-2 have the same circuit configuration.
For example, when a request event Req (1) is generated at the left side block 20-1 (corresponding to the logical level “H”), if the right side block 20-2 has not yet been activated and the response event Ack (2) has also not yet been generated (corresponding to the logic level “L”), then the response event Ack (1) is generated from the Muller C element with an inverter 10-1, and control for the logic circuit, which is not illustrated, is acquired. (This link is indicated by L1 in FIG. 9.)
The response event Ack (1) is delayed for a predetermined delay time DELAY 1 by the delay element 21-1, and becomes the request event Req (2) for the right side block 20-2. (This link is indicated by L2 in FIG. 9.)
Then the response event Ack (2) is also generated from the Muller C element with an inverter 10-2 in the right side block 20-2 based on the same logic, and the response event Ack (2) is fed back to the Muller C element with an inverter 10-1, so the response event Ack (1) loses the control thereof. (This link is indicated by L3 and L5 in FIG. 9.)
In other words, the response event Ack (1) generated from the Muller C element with an inverter 10-1 acquires control for the logic circuit, which is not illustrated, only during a predetermined delay time DELAY 1 of the delay element 21-1, and then the control is transferred to the response event Ack (2) generated from the Muller C element with an inverter 10-2.
The request event Req (1) itself also disappears after the delay time DELAY 0 of the delay element, which is not illustrated, in the left side block 20-0, which is not illustrated. (This is indicated by the link L4 in FIG. 9.) In the same way, the request event Req (2), which is output from the delay element 21-1, disappears after the delay time DELAY 1 in the left side block 20-1. (This is indicated by the link L6 in FIG. 9.)
When the request event Req (1) is generated in the left side block 20-1, however, the response event Ack (1) does not change at all due to the nature of the Muller C element with an inverter 10-2 if the right side block 20-2 has already been activated, and if the event Ack (2) has been generated. This is indicated by the link L3 (broken line) which became invalid in the event Ack (2) #1 and in the event Ack (1) #1 generated in the link L7 in FIG. 9.
Disappearance of the response event Ack (2) is also the same as the disappearance of the response event Ack (1), which disappears in the link L8 in FIG. 9 when the response event Ack (3) to be input to the Muller C element with an inverter 10-2 is received.
The meaning of the delay times DELAY 0, DELAY 1, and DELAY 2 in FIG. 9 is quite significant. If the delay times DELAY 0, DELAY 1 and DELAY 2 do not exist, then the delay time of the logic circuit to be controlled, which is not illustrated, cannot be secured. Therefore the request events Req (1), . . . and the response events Ack (1), . . . , which are transition signals, take charge, and as a result, asynchronous transition signaling cannot be implemented.
According to Document 1, the control circuit in FIG. 8 operates according to a simple stage state rule. In other words, if the state of the first or preceding block 20-2 and the next or succeeding block 20-1 are different, the state of the first block is transferred to the next block 20-1, otherwise the current state is maintained. For this stage state rule, a differential equation to define ocean waves and electro-magnetic waves is analogized. Actually, in the control circuit of the micro-pipeline in FIG. 8, one of the inverters of the Muller C elements with an inverter 10-1 and 10-2 is included in the loop where an event cycles around, so each loop oscillates, the request event Req (1) propagates to the right side in FIG. 8, and the response event Ack (1) propagates to the left side in FIG. 8.
For example, according to the timing waveform in FIG. 9, the response event Ack (1) transits to the response event Ack (2). In the control circuit in FIG. 8, an event generated in the left side block 20-1 is transferred to the right side block 20-2, so this operation is similar to an FIFO. Here, events are accumulated according to FIFO, and events which end in the left side block 20-1 are sequentially transferred to the right side block 20-2, . . . . Generally this operation is suitable for the control of a micro-pipeline.
In the case of the conventional control circuit of the micro-pipeline in FIG. 8, however, the problem is that the application range of asynchronous transition signaling using this conventional control circuit is narrow, as described in the following (a) and (b).
(a) The conventional control circuit of the micro-pipeline shown in FIG. 8 has a logic circuit structure where the control signal and the logic circuit to be controlled, which is not illustrated, are combined. Therefore in the control circuit of the micro-pipeline in FIG. 8, control becomes valid only during a predetermined delay time DELAY 1, . . . , then the control is propagated to the next block, just like a wave. As long as the logical delay time of the logic circuit to be controlled, which is not illustrated, does not exceed the propagation time of the control thereof, this asynchronous transition signaling functions effectively. However, in some cases the propagation of the control may not be an effective signal control. Generally, such a unit as a processor is comprised of devices having various input/output interfaces. And many of the devices cannot be included into asynchronous transition signaling since the upper limit delay time is not defined. A device which requires interrupt control, such as DMA (Direct Memory Access, which is direct data transfer between memories) and a timer, is an example of this type of device for which asynchronous transition signaling using the control circuit of the micro-pipeline in FIG. 8, cannot be used.
(b) FIG. 10 is a block configuration diagram of a conventional general bus arbitrator. In this bus arbitrator, a plurality of (N) number of devices, 30-1-30-N, such as memories, are connected to the common bus 31, and requests for use of this bus are arbitrated by the control circuit 32. When the common bus 31 is used, the devices 30-1-30-N output the device request signals Req 1-Req N to the control circuit 32. The control circuit 32 arbitrates contention of the device request signals Req 1-Req N. According to the arbitration, a device enabling signal (one of Grant 1-Grant N) is provided to one of the devices (30-1-30-N) according to the arbitration, so that this device uses the common bus 31 for a predetermined period, and the other devices standby for use.
The case when the control circuit 32 of such a bus arbitrator is comprised of the control circuit of the micro-pipeline in FIG. 8 is considered. Time to occupy the common bus 31 for the devices 30-1-30-N, which use the common bus 31, is irregular depending on the devices 30-1-30-N. Therefore generally the use of the control circuit of the micro-pipeline in FIG. 8 is inappropriate for such asynchronous transition signal control.